package demo.letcode.top100;

public class _79单词搜索 {
    public static void main(String[] args) {
        /**
         * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
         *
         * 输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"
         * 输出：true
         *
         * [A] [B] [C] E
         *  S   F  [C] S
         *  A  [D] [E] E
         *
         * 输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE"
         * 输出：true
         * A B  C   E
         * S F  C  [S]
         * A D [E] [E]
         *
         * 输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB"
         * 输出：false
         */

        m1();
    }

    private static void m1() {
        char[][] board = {
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}
        };
        String word = "ABCCED";
        int m = board.length, n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int x = 0; x < m; x++) {
            for (int y = 0; y < n; y++) {
                boolean flag = check(board, 0, x, y, word, visited); // 从每个点开始向四周每1步搜索
                if (flag) {
                    System.out.println(true);
                    return;
                }
            }
        }
        System.out.println(false);
    }

    private static boolean check(char[][] board, int idx, int x, int y, String word, boolean[][] visited) {
        if (board[x][y] != word.charAt(idx)) { // 如果 board[i][j]!=word[k]，当前字符不匹配，直接返回 false
            return false;
        } else if (idx == word.length() - 1) { // 如果当前已经访问到字符串的末尾，且对应字符依然匹配，此时直接返回 true。
            return true;
        }
        // 否则，遍历当前位置的所有相邻位置。如果从某个相邻位置出发，能够搜索到子串 word[k+1..]，则返回 true，否则返回 false
        int[][] dirs = {
                {1, 0}, {0, 1}, {-1, 0}, {0, -1}// 四周移动一个坐标
        };
        visited[x][y] = true;
        boolean ret = false;
        for (int[] dir : dirs) {
            int dx = x + dir[0];
            int dy = y + dir[1];

            if (dx >= 0 && dx < board.length && dy >= 0 && dy < board[0].length) {
                if (!visited[dx][dy]) {
                    boolean flag = check(board, idx + 1, dx, dy, word, visited);
                    if (flag) {
                        ret = true;
                        break;
                    }
                }
            }
        }
        visited[x][y] = false;// 回溯
        return ret;
    }
}
